package DataStr.homework03;
//根，左孩子，右孩子类
class BiNode{
    char val;
    BiNode lchild;
    BiNode rchild;
    public BiNode(char val){
        this.val=val;
        this.lchild=null;
        this.rchild=null;
    }
}
public class BiTree {
    BiNode root;//根节点
    public BiTree(String preOrder,String inOrder,int preIndex,int inIndex,int count){
        //preOrder:整棵树的先根遍历序列
        //inOrder:整棵树的中根遍历序列
        //preIndex:先根遍历序列在preOrder中的开始位置
        //inIndex:中根遍历序列在inIndex中的开始位置
        //count:树中结点的个数
        if(count>0){
            //现在先根遍历序列中找出根节点
            char ch=preOrder.charAt(preIndex);
            int i=0;
            //寻找根节点在中根序列中的位置
            for(;i<count;i++){
                if(ch==inOrder.charAt(i+inIndex)){
                    break;
                }
            }
            //建立树的根节点
            root=new BiNode(ch);
            //建立树的左孩子
            root.lchild= new BiTree(preOrder,inOrder,preIndex+1,inIndex,i).root;
            //建立树的右孩子
            root.rchild=new BiTree(preOrder,inOrder,preIndex+1+i,inIndex+i+1,count-i-1).root;
        }
    }
    //先根遍历
    public void print(BiNode root){
        if(root!=null) {
            System.out.print(root.val);
            print(root.lchild);
            print(root.rchild);
        }
    }
    public static void main(String[]args){
        String preOrder="ABHFDECKG";
        String inOrder="HBDFAEKCG";
        //创建Bitree对象
        BiTree b=new BiTree(preOrder,inOrder,0,0,preOrder.length());
        b.print(b.root);
    }
}
